package com.demo.贪心算法;

import cn.hutool.core.lang.Console;
import lombok.AllArgsConstructor;
import lombok.ToString;

import java.util.*;

/**
 * 求最大收益
 * @author cl
 */
public class MaxIncome {

    public static void main(String[] args) {
        List<MaxIncomeProject> projects = new ArrayList<>();
        projects.add(new MaxIncomeProject("项目1", 2, 1));
        projects.add(new MaxIncomeProject("项目2", 3, 2));
        projects.add(new MaxIncomeProject("项目3", 2, 2));
        projects.add(new MaxIncomeProject("项目4", 3, 3));
        projects.add(new MaxIncomeProject("项目5", 8, 4));
        projects.add(new MaxIncomeProject("项目6", 4, 2));
        projects.add(new MaxIncomeProject("项目7", 16, 10));
        List<MaxIncomeProject> ret = getBestIncomeProject(projects, 2, 4);
        Console.log("启动资金为2, 只能做4个项目, 最优的解决按收益是： {}， 方案如下：", ret.stream().mapToInt(o->o.income).sum() + 2);
        ret.forEach(System.out::println);
    }

    /**
     * 获取最佳投资方案
     * @param projects 所有可以做的项目
     * @param startMoney 启动金
     * @param count 可以投资的次数
     * @return
     */
    public static List<MaxIncomeProject> getBestIncomeProject(List<MaxIncomeProject> projects, int startMoney, int count) {
        if (projects == null || projects.isEmpty()) {
            return projects;
        }
        List<MaxIncomeProject> result = new ArrayList<>();
        // 投资最小堆
        PriorityQueue<MaxIncomeProject> investHeap = new PriorityQueue<>(Comparator.comparingInt(o -> o.invest));
        investHeap.addAll(projects);
        // 收益最大堆
        PriorityQueue<MaxIncomeProject> incomeHeap = new PriorityQueue<>((o1, o2) -> Integer.compare(o2.invest + o2.income, o1.invest + o1.income));
        for (int i = 0; i < count; i++) {
            // 弹出所有启动金小于的项目
            while (!investHeap.isEmpty() && investHeap.peek().invest <= startMoney) {
                // 添加到投资项目中
                incomeHeap.add(investHeap.poll());
            }
            if (incomeHeap.isEmpty()) {
                break;
            }
            MaxIncomeProject tmp = incomeHeap.poll();
            result.add(tmp);
            startMoney += tmp.income;
        }
        return result;
    }

    @ToString
    @AllArgsConstructor
    public static class MaxIncomeProject {
        // 项目名
        public String name;
        // 投资
        public Integer invest;
        // 收益
        public Integer income;
    }
}
